package code1.dp;

/**
 * 原题链接：https://leetcode.cn/problems/target-sum/
 */
public class P494 {


    //设取正号的数的和为x，则取负号的数的和为sum-x, 有x-(sum-x)=target，得x=(target+sum)/2
    //转化为选取数使其和为x共有多少种选法
    //0-1背包问题,dp[j]表示装满容量为j的背包有多少种装法
    //此类问题的递推公式为：dp[j] += dp[j - nums[i]];
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if( (target+sum)%2!=0 || Math.abs(target)>sum){
            return 0;       //没有方案
        }
        int size=(target+sum)/2;
        int[] dp=new int[size+1];
        dp[0]=1;            //初始化
        for(int i=0;i<nums.length;i++){
            for(int j=size;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];           //装满j-nums[i]共有dp[j-nums[i]]种装法，装上nums[i]就装满了j
            }
        }
        return dp[size];
    }
}
